package hanjia;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/15-下午4:36
 * Since  :   1.0
 * Version:   1.0
 */
public class LeetCode51 {

    public List<List<String>> solveNQueens(int n) {

        char[][] chessboard = new char[n][n];
        int row = 0;
      for (char[] c:chessboard){
          Arrays.fill(c,'.');
      }
        List<List<String>> results = new ArrayList<>();
        backtracking(chessboard, row, n, results);
        return results;


    }

    private void backtracking(char[][] chessboard, int row, int n, List<List<String>> results) {
        if (row == n) {
            results.add(charToList(chessboard));
        }

        for (int col=0;col<n;col++){
            if (isValid(col,row,chessboard)){
                chessboard[row][col]='Q';
                backtracking(chessboard,row+1,n,results);
                chessboard[row][col]='.';

            }

        }





    }

    private boolean isValid(int col, int row, char[][] chessboard) {

        for (int i=0;i<row;i++){
            if (chessboard[i][col]=='Q'){
                return false;
            }
        }

        for (int i=row-1, j=col-1;i>=0&&j>=0;i--,j--){
            if (chessboard[i][j]=='Q')
                return false;
        }
        for (int i=row-1,j=col+1;i>=0&&j<chessboard.length;i--,j++){
            if (chessboard[i][j]=='Q')
                return false;
        }
        return true;



    }

    private List<String> charToList(char[][] chessboard) {
        ArrayList<String> result = new ArrayList<>();
        for (char [] chess:chessboard){
            result.add(new String(chess));
        }
        return result;


    }


}
